# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# kotlin 版的效率还不错，python3 版的居然超时了
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        li1, li2 = l1, l2
        result, curr = None, None
        while li1 != None or li2 != None:
            [minVal, newLi1, newLi2] = self.__findMin(li1, li2)
            if curr == None:
                curr = ListNode(minVal)
                result = curr
            else:
                curr.next = ListNode(minVal)
                curr = curr.next
        li1, li2 = newLi1, newLi2
        return result

    def __findMin(self, l1: ListNode, l2: ListNode):
        if l1 == None:
            return [l2.val, l1, l2.next]
        elif l2 == None:
            return [l1.val, l1.next, l2]
        elif l1.val < l2.val:
            return [l1.val, l1.next, l2]
        else:
            return [l2.val, l1, l2.next]